<?php
/**
 * @title 75. 颜色分类 - 双指针1次遍历
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function sortColors(&$nums) {
        /**
         * @since 2020-10-12 指针0, 指针2位置
         */
        $p0 = 0;
        $p2 = count($nums)-1;

        /**
         * @since 2020-10-13 1次遍历, 0放头部, 2放尾部
         */
        for($i=0; $i<=$p2; $i++){
            if($nums[$i] == 0){
                /**
                 * @since 2020-10-13 移动到头部
                 * @since 2020-10-13 从头部不可能换个2回来, 如果是2, 一定会被换到尾部
                 */
                // if($i !== $p0){
                    $nums[$i] = $nums[$p0];
                    $nums[$p0] = 0;
                    // $i--;
                // } else {}

                $p0++;
            } elseif($nums[$i] == 2) {
                /**
                 * @since 2020-10-13 移动到尾部
                 * @since 2020-10-13 可能会换 2 或者 0 回来, 因此i指针不变
                 */
                $nums[$i] = $nums[$p2];
                $nums[$p2] = 2;
                $i--;
                $p2--;

                // /**
                //  * @since 2020-10-13 移动到尾部
                //  * @since 2020-10-13 找到一个非2交换
                //  */
                // for(; $p2>$i; $p2--){
                //     if($nums[$p2] !== 2){
                //         $nums[$i] = $nums[$p2];
                //         $nums[$p2] = 2;
                //         $p2--;
                //         $i--;
                //         break;
                //     } else {}
                // }
            } else {
                /**
                 * @since 2020-10-13 不操作
                 */
            }
        }

        /**
         * @return
         */
        return $nums;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.05_5.php
 */
$datas = [
    [2,0,2,1,1,0],
    [1,2,2,2,2,0,0,0,1,1],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->sortColors($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
